import json
InputStr = '''
[
  {
    "node": "=",
    "children": [
      {
        "node": "S"
      },
      {
        "node": "+",
        "children": [
          {
            "node": "*",
            "children": [
              {
                "node": "X"
              },
              {
                "node": "2"
              }
            ]
          },
          {
            "node": "*",
            "children": [
              {
                "node": "A"
              },
              {
                "node": "+",
                "children": [
                  {
                    "node": "Y"
                  },
                  {
                    "node": "1"
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
]
'''
# 将JSON格式输入字符串转换为Python数据类型
InputDataTree = json.loads(InputStr)
print(InputDataTree)
# output:
#[{'node': '=', 'children': [{'node': 'S'}, {'node': '+', 'children': [{'node': '*', 'children': [{'node': 'X'}, {'node': '2'}]}, {'node': '*', 'children': [{'node': 'A'}, {'node': '+', 'children': [{'node': 'Y'}, {'node': '1'}]}]}]}]}]

# 给定的嵌套字典结构
data = [{'node': '=', 'children': [{'node': 'S'}, {'node': '+', 'children': [{'node': '*', 'children': [{'node': 'X'},{'node': '2'}]}, {'node': '*', 'children': [{'node': 'A'}, {'node': '+', 'children': [{'node': 'Y'}, {'node': '1'}]}]}]}]}]

# 遍历InputDataTree，并打印每个节点的值


def traverse(node):
    # 打印当前节点的值
    print(node['node'])
    # 如果存在children，则递归遍历每一个子节点
    if 'children' in node:
        for child in node['children']:
            traverse(child)


# 开始遍历
traverse(data[0])


def to_postfix(node):
    """
    将中缀表达式树转换为后缀表达式（逆波兰表达式）。

    Args:
        node (dict): 中缀表达式树的节点，包含'node'键和'children'键。'node'键存储节点值（操作符或操作数），'children'键存储子节点列表。

    Returns:
        str: 转换后的后缀表达式。

    """
    postfix = ""
    if 'children' in node:
        # 递归处理子节点
        for child in node['children']:
            postfix += to_postfix(child)
        # 添加当前节点的值（操作符）
        postfix += node['node']
    else:
        # 如果没有子节点，直接添加节点值（操作数）
        postfix += node['node']
    return postfix


# 将树转换为后缀表达式
postfix_expression = to_postfix(data[0])
print(postfix_expression)
# output:
# SX2*AY1+*+=


# 给定的后缀表达式
postfix_expression = "SX2*AY1+*+="

# 将后缀式转换为三元式
def to_triplet(postfix_expr):
    stack = []
    triplets = []
    operators = ['+', '-', '*', '/', '=']
    operatorsBinary = ['+', '-', '*', '/']
    seq = 1  # 初始化三元式编号
    for token in postfix_expr:
        if token not in operators:  # 非运算符
            stack.append(token)
        if token in operators:  # 运算符
            if token in operatorsBinary:  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()
                noStr = '(' + str(seq) + ')'
                seq = seq + 1
                triplets.append((noStr, token, opnd1, opnd2))
                stack.append(noStr)
            if token == '=':  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()               
                noStr = '(' + str(seq) + ')'
                seq = seq + 1
                triplets.append((opnd1, token, opnd2, "null"))
                stack.append(noStr)

    return triplets


# 将后缀表达式转换为三元式
triplets = to_triplet(postfix_expression)
print(triplets)
# output
# [
# ('(1)', '*', 'X', '2'), 
# ('(2)', '+', 'Y', '1'), 
# ('(3)', '*', 'A', '(2)'), 
# ('(4)', '+', '(1)', '(3)'), 
# ('S', '=', '(4)', 'null')
# ]


# 给定的后缀表达式
postfix_expression = "SX2*AY1+*+="

# 将后缀式转换为四元式
def to_quadruple(postfix_expr):
    stack = []
    triplets = []
    operators = ['+', '-', '*', '/', '=']
    operatorsBinary = ['+', '-', '*', '/']
    seq = 1  # 初始化三元式编号
    for token in postfix_expr:
        if token not in operators:  # 非运算符
            stack.append(token)
        if token in operators:  # 运算符
            if token in operatorsBinary:  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()
                noStr = 'T' + str(seq) 
                seq = seq + 1
                triplets.append((token, opnd1, opnd2,noStr))
                stack.append(noStr)
            if token == '=':  # 二元运算符
                opnd2 = stack.pop()
                opnd1 = stack.pop()               
                noStr = 'T' + str(seq) 
                seq = seq + 1
                triplets.append((token,opnd1,  opnd2, opnd1))
                stack.append(noStr)

    return triplets


# 将后缀表达式转换为三元式
triplets = to_quadruple(postfix_expression)
print(triplets)
# output
# [
# ('*', 'X', '2', 'T1'), 
# ('+', 'Y', '1', 'T2'), 
# ('*', 'A', 'T2', 'T3'), 
# ('+', 'T1', 'T3', 'T4'), 
# ('=', 'S', 'T4', 'S')
# ]  